package com.njts.array;

import java.util.Random;
import java.util.Scanner;

/**
 * @author David GE
 * Date  2025/11/13
天平找假币 计算思维

给定 n 枚外观相同的硬币，其中恰有 1 枚是假币且更轻(可用随机数生成)。你可以使用**无砝码的天平**进行称重：一次称重可将若干枚硬币分别放在天平左右两盘，天平会返回三种结果之一：

- 左重（左盘更重）
- 右重（右盘更重）
- 相等
- 解空间(状态)
- [log3N]

请设计一个算法，**最少数量级**地确定哪一枚是假币，并输出其下标。

输入

- 第一行：整数 n


输出

- 一行：`index=<假币下标> weighs=<称重次数>`


 */
public class CoinWeight {
    public static void main(String[] args) {
        Scanner scanner =new Scanner(System.in);
        // 用数组模拟硬币重量,硬币编号就是数组的下标
        int n = scanner.nextInt();
        // 假设 真 重量 1 假币 重量为0

        int[] coins = new int[n];
        for (int i = 0; i < n; i++) {
            coins[i]=1;
        }
        // 用随机数生成假币的位置
        Random random = new Random();
        int index = random.nextInt(n);
        coins[index]=0;
        // 解题,假设index未知,找出index
        // 重量和硬币数 并不相等 区间长度不一定能被正好等分,某个区间会多一个硬币
        // 10 0-2 3-6 7-10
        // 即使在等分的情况下,重量也有可能比区间长度少
        // 不能简单对整个区间切分
        // 只有两枚硬币->忽略 n=n/3
        // 正解,动态记录区间端点,
        int targetIndex =0;
        // [0,n/3)  [n/3,2n/3),[2n/3,3n/3)
        int w1=0;
        int w2=0;
        int endIndex =n;//假硬币所在子区间的右端点 n 2 endIndex=2n/3  endindex=endindex*2/3
        // n==1时,当前下标就是假币所在
        if (endIndex-targetIndex==1){
            System.out.println("index=0,weights=1");
            return;
        }
        int weights=0;
        while (endIndex-targetIndex>1) {
            weights++;
            //考虑只有两枚的情况
            if (endIndex-targetIndex==2){
                if (coins[targetIndex]<coins[endIndex-1]){
                    System.out.println("index="+targetIndex+"\t"+"weights="+weights);

                }else{
                    System.out.println("index="+targetIndex+"\t"+"weights="+weights);


                }
                System.out.println(index);
                return;
            }
            // 计算每个区间的重量(分区)
            //重量不能和长度混淆(想当然)
            w1=0;
            w2=0;
            int sizeA = (endIndex-targetIndex) / 3;
            int sizeB = (endIndex-targetIndex) / 3;
            int aL = targetIndex;//[0,ar)
            int aR = targetIndex + sizeA;
            int bL = aR;//[ar,br)
            int bR = aR + sizeB;
            int cL = bR;
            int cR = endIndex;
            for (int i = aL; i <aR ; i++) {
                    w1=w1+coins[i];
            }

            for (int i = bL; i <bR ; i++) {
                w2=w2+coins[i];

            }
            // 比较天平两端个重量大小
            if (w1 == w2) {
                targetIndex = cL;
                endIndex=cR;
            }
           else  if (w1 < w2) {
                targetIndex =aL;
                endIndex=aR;
            }
           else  if (w1>w2) {
                targetIndex = bL;
                endIndex=bR;
            }


        }
        System.out.println(index);
        System.out.println("index="+targetIndex+"\t"+"weights="+weights);




    }
}
